﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace 编译原理
{
    public static class 实验二
    {
        #region 变量
        class Production
        {
            public Production()
            {
                rights = new List<string>();
                first = new List<char>();
                last = new List<char>();
                visit = new List<char>();
            }
            public char left { get; set; }
            public List<string> rights { get; set; }
            public List<char> first { get; set; }
            public List<char> last { get; set; }
            public List<char> visit { get; set; }
        }
        //产生式
        static List<Production> productions { get; set; } = new List<Production>();
        //算符优先关系表
        static List<List<char>> PrecedenceTable { get; set; } = new List<List<char>>();
        //终结符字典 下标映射 
        static Dictionary<char, int> Terminator { get; set; } = new Dictionary<char, int>();
        //非终结符集合
        static List<char> NonTerminator { get; set; } = new List<char>() { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
        //分析栈
        static string mStack { get; set; } = "";
        //待分析字符串队列
        static string mQueue { get; set; } = "";
        #endregion
        public static void 算符优先分析()
        {
            ReadFile();
            GetFirstVtAndLastVt();
            GetOperatorPrecedenceTable();
            Analyse();
        }
        #region 读取文法
        static void ReadFile()
        {
            try
            {
                using (StreamReader sr = new StreamReader("../../file1.txt"))
                {
                    string line;
                    while ((line = sr.ReadLine()) != null)
                    {
                        //Console.WriteLine(line);
                        var tempLine = line.Split(' ', '|');
                        var tempProduction = new Production();
                        tempProduction.left = tempLine[0][0];
                        for (int i = 2; i < tempLine.Length; i++)
                        {
                            tempProduction.rights.Add(tempLine[i]);
                        }
                        productions.Add(tempProduction);
                    }
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("The file could not be read:");
                Console.WriteLine(e.Message);
            }
            //输出
            Console.WriteLine($"-----扩展文法-----------------");
            foreach (var item in productions)
            {
                foreach (var item2 in item.rights)
                {
                    Console.WriteLine($"{item.left} -> {item2}");
                }
            }
            Console.WriteLine();
        }
        #endregion
        #region FirstVt集 LastVt集
        static void GetFirstVtAndLastVt()
        {
            foreach (var item in productions)
            {
                item.visit.Clear();
                DfsForFirstVt(item, item);
                item.visit.Clear();
                DfsForLastVt(item, item);
                item.visit.Clear();
            }
            //输出FirstVt集
            Console.WriteLine($"-----FirstVt:-----------------");
            foreach (var item in productions)
            {
                Console.Write($"{item.left} : ");
                foreach (var item2 in item.first)
                {
                    Console.Write($" {item2}");
                }
                Console.WriteLine();
            }
            //输出LastVt集
            Console.WriteLine($"-----LastVt:------------------");
            foreach (var item in productions)
            {
                Console.Write($"{item.left} : ");
                foreach (var item2 in item.last)
                {
                    Console.Write($" {item2}");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
        //深度优先搜索求FirstVt集
        static void DfsForFirstVt(Production p1, Production p2)
        {
            p2.visit.Add(p1.left);
            foreach (var item in p1.rights)
            {
                //如果第一位是非终结符
                if (item[0] >= 'A' && item[0] <= 'Z')
                {
                    int cnt = 0;
                    //如果第二位是终结符
                    foreach (var item3 in item)
                    {
                        if (item3 >= 'A' && item3 <= 'Z') continue;
                        p2.first.Add(item3);
                        if (cnt++ > 0) break;
                    }
                    //去环
                    if (p2.visit.Contains(item[0])) continue;
                    //
                    foreach (var item2 in productions)
                    {
                        if (item2.left == item[0])
                        {
                            DfsForFirstVt(item2, p2);
                        }
                    }
                }
                else
                {
                    p2.first.Add(item[0]);
                }
            }
        }
        //深度优先搜索求LastVt集
        static void DfsForLastVt(Production p1, Production p2)
        {
            p2.visit.Add(p1.left);
            foreach (var item in p1.rights)
            {
                string temp = "";
                foreach (var item1 in item.Reverse())
                {
                    temp += item1;
                }
                //如果第一位是非终结符
                if (temp[0] >= 'A' && temp[0] <= 'Z')
                {
                    int cnt = 0;
                    //找第一个终结符
                    foreach (var item3 in temp)
                    {
                        if (item3 >= 'A' && item3 <= 'Z') continue;
                        p2.last.Add(item3);
                        if (cnt++ > 0) break;
                    }
                    //去环
                    if (p2.visit.Contains(temp[0])) continue;
                    //将非终结符的LastVt加入进来
                    foreach (var item2 in productions)
                    {
                        if (item2.left == temp[0])
                        {
                            DfsForLastVt(item2, p2);
                        }
                    }
                }
                else
                {
                    p2.last.Add(temp[0]);
                }
            }
        }
        #endregion
        #region 算符优先关系表

        //收集终结符
        static void CollectTerminators()
        {
            int terminatorIndex = 0;
            foreach (var item in productions)
            {
                foreach (var str in item.rights)
                {
                    foreach (var c in str)
                    {
                        if (NonTerminator.Contains(c)) continue;
                        if (Terminator.ContainsKey(c)) continue;
                        Terminator.Add(c, ++terminatorIndex);
                    }
                }
            }
        }
        //初始化算符优先关系表
        static void InitOperatorPrecedenceTable()
        {
            PrecedenceTable.Add(new List<char>() { ' ' });
            foreach (var item in Terminator)
            {
                PrecedenceTable[0].Add(item.Key);
            }
            foreach (var item in Terminator)
            {
                PrecedenceTable.Add(new List<char>() { item.Key });
            }
            for (int i = 1; i < PrecedenceTable.Count; i++)
            {
                foreach (var item2 in Terminator)
                {
                    PrecedenceTable[i].Add(' ');
                }
            }
        }
        static void GetOperatorPrecedenceTable()
        {
            CollectTerminators();
            InitOperatorPrecedenceTable();
            foreach (var item in productions)
            {
                foreach (var str in item.rights)
                {
                    for (int i = 0; i < str.Length; i++)
                    {
                        for (int j = i + 1; j < str.Length; j++)
                        {
                            if (NonTerminator.Contains(str[i]))
                            {
                                if (NonTerminator.Contains(str[j]))
                                {

                                }
                                else
                                {
                                    if (j > i + 1) continue;
                                    foreach (var production in productions)
                                    {
                                        if (production.left == str[i])
                                        {
                                            foreach (var last in production.last)
                                            {
                                                if (PrecedenceTable[Terminator[last]][Terminator[str[j]]] == ' ')
                                                {
                                                    PrecedenceTable[Terminator[last]][Terminator[str[j]]] = '>';
                                                }
                                            }
                                        }
                                    }
                                }
                            }
                            else
                            {
                                if (NonTerminator.Contains(str[j]))
                                {
                                    if (j > i + 1) continue;
                                    foreach (var production in productions)
                                    {
                                        if (production.left == str[j])
                                        {
                                            foreach (var first in production.first)
                                            {
                                                if (PrecedenceTable[Terminator[str[i]]][Terminator[first]] == ' ')
                                                {
                                                    PrecedenceTable[Terminator[str[i]]][Terminator[first]] = '<';
                                                }
                                            }
                                        }
                                    }
                                }
                                else
                                {

                                    if (PrecedenceTable[Terminator[str[i]]][Terminator[str[j]]] == ' ')
                                    {
                                        PrecedenceTable[Terminator[str[i]]][Terminator[str[j]]] = '=';
                                    }
                                }
                            }
                        }
                    }
                }
            }
            //输出
            Console.WriteLine($"-----算符优先关系表-----------");
            foreach (var item1 in PrecedenceTable)
            {

                foreach (var item2 in item1)
                {
                    Console.Write($" {item2} ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
        #endregion
        #region 分析句子
        //分析初始化
        static void Analyse()
        {
            Console.WriteLine($"-----分析句子-----------------");
            //待分析句子
            List<string> list = new List<string>()
            {
                "(i+i)*i#",
                "i+i)*i#",
            };
            foreach (var item in list)
            {
                Console.WriteLine($"--- {item} ---");
                if (AnalyseProcess(item))
                {
                    Console.WriteLine("识别成功");
                }
                else
                {
                    Console.WriteLine("识别失败");
                }
                Console.WriteLine();
            }
        }
        //分析过程
        static bool AnalyseProcess(string s)
        {
            mStack = "";
            mQueue = $"#{s}";

            while (mQueue.Length > 0)
            {
                if (mStack.Equals("") || NonTerminator.Contains(mStack.Last()))
                {
                    IntoTheStack();
                }
                else
                {
                    var c = PrecedenceTable[Terminator[mStack.Last()]][Terminator[mQueue[0]]];
                    if (c == '=' || c == '<')
                    {
                        IntoTheStack();
                    }
                    else if (c == '>')
                    {
                        if (!Reduce()) { return false; }
                    }
                }
            }
            while (mStack != productions[0].rights[0])
            {
                if (!Reduce()) { return false; }
            }
            return true;
        }
        //进栈
        static void IntoTheStack()
        {
            mStack += mQueue[0];
            mQueue = mQueue.Remove(0, 1);
            Console.WriteLine($"{mStack}\t\t{mQueue}\t\t进栈");
        }
        //归约
        static bool Reduce()
        {
            List<string> canReduce = new List<string>();
            List<char> reduceTo = new List<char>();
            foreach (var production in productions)
            {
                foreach (var right in production.rights)
                {
                    if (mStack.Contains(right))
                    {
                        canReduce.Add(right);
                        reduceTo.Add(production.left);
                    }
                }
            }
            if (canReduce.Count == 0) return false;
            int idx = 0;
            for (int i = 0; i < canReduce.Count; i++)
            {
                foreach (var item in canReduce[i])
                {
                    if (Terminator.ContainsKey(item))
                    {
                        idx = i;
                        break;
                    }
                }
            }
            for (int i = 0; i < mStack.Length; i++)
            {
                if (mStack[i] == canReduce[idx][0])
                {
                    mStack = mStack.Remove(i, canReduce[idx].Length).Insert(i, reduceTo[idx].ToString());
                    break;
                }
            }
            Console.WriteLine($"{mStack}\t\t{mQueue}\t\t归约");
            return true;
        }
        #endregion
    }
}
